class Solution {
public:
/*
  // 滑动窗口（双指针） O(n) O(1)
    int minSubArrayLen(int target, vector<int>& nums) {
        // 找出和满足≥ target的最短连续子数组
        int minLen = nums.size()+1;  // 返回结果
        int sum = 0; // 当前子序列（窗口）的和

        int left = 0;
        for(int right = 0; right < nums.size(); ++right){
            sum += nums[right];
            while(sum >= target){
                // 更新最短长度
                minLen = minLen < (right-left+1) ? minLen : (right-left+1);
                // 移动left
                sum -= nums[left++];
            }
        }
        return (minLen > nums.size()) ? 0 : minLen;
    }
*/
   /** 因为这道题保证了数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正，这里就不能使用二分来查找这个位置了。
   C++ 的 lower_bound 函数来为我们实现这里二分查找大于等于某个数的第一个位置的功能 **/

    // 前缀和 O(nlogn) O(n)
    int minSubArrayLen(int target, vector<int>& nums) {
        int minLen = nums.size()+1;  // 返回结果
        vector<int> sum(minLen, 0);  //前缀和
        for(int i = 1; i <= nums.size(); ++i)
            sum[i] = sum[i-1]+nums[i-1];
        for(int i = 1; i <= nums.size(); ++i){
            int s = target + sum[i-1];
            auto bound = lower_bound(sum.begin(), sum.end(), s);
            if (bound != sum.end()) {
                minLen = min(minLen, static_cast<int>((bound-sum.begin())-i+1));
            }
        }
         return (minLen > nums.size()) ? 0 : minLen;
    }
    /* 我们只需要找到 sums[k]-sums[j]>=s，那么 k-j 就是满足的连续子数组，但不一定是最小的，所以我们要继续找，直到找到最小的为止。怎么找呢，我们可以使用两个 for 循环来枚举，但这又和第一种暴力求解一样了，所以我们可以换种思路，求 sums[k]-sums[j]>=s 我们可以求 sums[j]+s<=sums[k]，那这样就好办了，因为数组sums中的元素是递增的，也就是排序的，我们只需要求出 sum[j]+s 的值，然后使用二分法查找即可找到这个 k  **/

};